package com.sword.www.leetCode.hard;

/**
 * https://leetcode-cn.com/problems/first-missing-positive/
 * 41. 缺失的第一个正数
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 *
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,0]
 * 输出：3
 * 示例 2：
 *
 * 输入：nums = [3,4,-1,1]
 * 输出：2
 * 示例 3：
 *
 * 输入：nums = [7,8,9,11,12]
 * 输出：1
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 5 * 105
 * -231 <= nums[i] <= 231 - 1
 *
 * @author linmeng
 * @version 1.0
 * @date 2022年1月3日 17:22
 */
public class L_41 {
    public static void main(String[] args) {
        int[] nums = {3,4,-1,1};
        System.out.println(firstMissingPositive2(nums));
    }
    /**
     * 寻找缺失的第一个正数
     * 有两种情况，第一种情况是有负数或有大于数组长度的数，这个时候缺失的数字肯定在1到数组长度中间
     *            第二种情况是没有负数或有大于数组长度的数，缺失的数组就是数组长度+1
     *  解法一：
     *      遍历数组，将小于等于0的和大于n+1的数改为n+1
     *      遍历数组，将出现的数字在n-1角标下改为负数
     *      遍历数组，第一个不为负数的元素就直接返回角标+1
     *
     * @param nums 数组
     * @author linmeng
     * @date 2022年1月3日 17:23
     * @return int
     */
    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i]<=0 || nums[i] > n){
                nums[i] = n+1;
            }
        }
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num < n+1 && nums[num-1] > 0){
                nums[num-1] = - nums[num-1];
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i]>0){
                return i+1;
            }
        }
        return n+1;
    }

    /**
     * 解法：
     *      元素置换，将nums[i] 置换到角标值为nums[i]-1的位置，如果两个元素相同就跳过
     *
     * @param nums 数组
     * @author linmeng
     * @date 2022年1月3日 17:53
     * @return int
     */
    public static int firstMissingPositive2(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i]>0 && nums[i] <=n && nums[i]!=nums[nums[i]-1]){
                int tmp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = tmp;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]!=i+1){
                return i+1;
            }
        }
        return n+1;
    }
}
